package com.cb2.algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/maximum-binary-tree/">最大二叉树(Maximum Binary Tree)</a>
 * <p>给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 * <ol>
 *     <li>创建一个根节点，其值为 nums 中的最大值。</li>
 *     <li>递归地在最大值 左边 的 子数组前缀上 构建左子树。</li>
 *     <li>递归地在最大值 右边 的 子数组后缀上 构建右子树。</li>
 * </ol>
 * </p>
 * <p>返回 nums 构建的 最大二叉树 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [3,2,1,6,0,5]
 *                       6
 *                     /   \
 *                    3     5
 *                     \   /
 *                      2 0
 *                      \
 *                       1
 *      输出：[6,3,5,null,2,0,null,null,1]
 *      解释：递归调用如下所示：
 *          - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 *              - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 *                  - 空数组，无子节点。
 *                  - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 *                      - 空数组，无子节点。
 *                      - 只有一个元素，所以子节点是一个值为 1 的节点。
 *              - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 *                  - 只有一个元素，所以子节点是一个值为 0 的节点。
 *                  - 空数组，无子节点。
 *
 * 示例 2：
 *      输入：nums = [3,2,1]
 *                      3
 *                       \
 *                        2
 *                         \
 *                          1
 *      输出：[3,null,2,null,1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 1000</li>
 *     <li>0 <= nums[i] <= 1000</li>
 *     <li>nums 中的所有整数 互不相同</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/10 16:44
 */
public class LC0654ConstructMaximumBinaryTree_M {
    static class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            return constructMaximumBinaryTree(nums, 0, nums.length - 1);
        }

        private TreeNode constructMaximumBinaryTree(int[] nums, int leftBoundary, int rightBoundary) {
            if (leftBoundary > rightBoundary) {
                return null;
            }
            int maxElementIndex = getMaxElementIndex(nums, leftBoundary, rightBoundary);
            TreeNode root = new TreeNode(nums[maxElementIndex]);
            root.left = constructMaximumBinaryTree(nums, leftBoundary, maxElementIndex - 1);
            root.right = constructMaximumBinaryTree(nums, maxElementIndex + 1, rightBoundary);
            return root;
        }

        private int getMaxElementIndex(int[] nums, int leftBoundary, int rightBoundary) {
            int maxElementIndex = leftBoundary;
            for (int i = leftBoundary + 1; i <= rightBoundary; i++) {
                if (nums[i] > nums[maxElementIndex]) {
                    maxElementIndex = i;
                }
            }
            return maxElementIndex;
        }

        /**
         * <a href='https://leetcode.cn/problems/maximum-binary-tree/solutions/1/zhua-wa-mou-si-by-muse-77-myd7/'>单调栈的实现方式</a>
         */
        public TreeNode constructMaximumBinaryTree2(int[] nums) {
            Deque<TreeNode> helper = new LinkedList<>();
            for (int i = 0; i < nums.length; i++) {
                TreeNode currNode = new TreeNode(nums[i]);
                while (!helper.isEmpty()) {
                    TreeNode topNode = helper.peekLast();
                    if (topNode.val > currNode.val) {
                        helper.addLast(currNode);
                        topNode.right = currNode;
                        break;
                    } else {
                        helper.removeLast();
                        currNode.left = topNode;
                    }
                }
                if (helper.isEmpty()) {
                    helper.addLast(currNode);
                }
            }
            return helper.peek();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printTreeNode(solution.constructMaximumBinaryTree2(new int[]{3, 2, 1, 6, 0, 5}));
    }
}
